package com.yitau.sort;

import com.yitau.utils.ArrayUtils;

/**
 * 选择排序
 */
public class SelectSort {

    /**
     * 1.首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
     * 2.再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾
     * 3.重复第二步，直到所有元素均排序完毕
     * 默认由小到大排序
     * @param array 原数组，执行完后数组内容改变
     */
    public static void selectSort(int[] array) {
        ArrayUtils.printArray(array, 0);
        // 最多排序 (array.length - 1) 趟
        for (int i = 0; i < array.length - 1; i++) {
            // 从 i 开始
            int min = i;
            for (int j = i + 1; j < array.length; j++) {
                // 从i开始往后找最小的数
                if (array[j] < array[min]) {
                    min = j;
                }
            }
            // 将最小值交换到 i的位置
            if (min != i) {
                ArrayUtils.swap(array, i, min);
            }
            ArrayUtils.printArray(array, i + 1);
        }
    }

    public static void main(String[] args) {
        // write your code here
        System.out.println("正序：");
        selectSort(ArrayUtils.DEFAULT_ARRAY_ASC);
        System.out.println("逆序：");
        selectSort(ArrayUtils.DEFAULT_ARRAY_DESC);
        System.out.println("随机：");
        selectSort(ArrayUtils.DEFAULT_ARRAY_RANDOM);
    }
}
